
在学习之前请先学习  分块 。

打表大家都知道，就是在比赛时把答案都输出出来，然后开个数组，把答案直接存入数组里。于是你的代码时间复杂度就是 $O(1)$ 的了。

但是需要注意这个技巧只适用于类似输出某函数值类的问题。比如规定 $f(x)$ 为整数 $x$ 的二进制表示中 $1$ 的个数。输入一个正整数 $n$，输出 $\sum_{i=1}^nf^2(i)$。这样的话 $n$ 不大时，采用打表的方法可以做到 $O(1)$ 的复杂度。

注意到这个问题其实十分的简单，采用一般做法也可以做到 $O(n\log n)$ 的复杂度，但是 $n=10^9$？

还有一些时候，打出来的表十分大，如果对于每一个 $n$，都输出 $f(n)$ 的话，那么 MLE 之外，还有可能代码超过最大代码长度限制，导致编译前不通过（代码可能直接被 pass）。

我们考虑优化这个答案表，借用分块思想，我们设置一个合理的步长 $m$（这个步长一般视代码长度而定），对于第 $i$ 块，输出：

$$
\Large \sum_{k=\frac{n}{m}(i-1)+1}^{\frac{ni}{m}} f^2(k)
$$

的值。

然后输出答案时借用分块思想处理即可。

一般来说，这样的问题对于处理单个函数值 $f(x)$ 很快，但是需要大量函数值求和（求积或某些可以快速合并的操作），枚举会超出时间限制，在找不到标准做法的情况下，分段打表是一个不错的选择。

\subsubsection{注意事项}

\begin{enumerate}
\item 当上题中指数不是定值，但是范围较小，也可以考虑打表；
\item 上题是本人为了介绍分段打表口胡出来的，如已有此题纯属巧合。
\end{enumerate}

\subsubsection{例题}

\href{https://www.lydsy.com/JudgeOnline/problem.php?id=3798}{「BZOJ 3798」特殊的质数}：权限题……\sout{不过可以在各大 BZ 离线题库中看到。}

\href{https://www.zhihu.com/question/60674478/answer/180805562}{题意简述}：求 $[l,r]$ 区间内有多少个质数可以分解为两个正整数的平方和。—— via PoPoQQQ

\href{https://www.luogu.org/problem/show?pid=P1822}{「Luogu P1822」魔法指纹}：其实是一道暴搜，不过可以练练分段打表。

